package algorithm.子数组达到规定累加和的最大长度系列问题;

import java.util.Arrays;
import java.util.List;

public class LongestLessSumSubArrayLength {


    //建立以某个位置作为子数组的“开始位置”的思路
    public static int getMaxLength(int[] arr, int K){
        Integer[] minSum = new Integer[arr.length];
        Integer[] minIndex = new Integer[arr.length];
        minSum[arr.length - 1] = arr[arr.length - 1];
        minIndex[arr.length - 1] = arr.length;
        for (int i = arr.length - 2; i >= 0; i--) {
            int sum = 0;
            int index = i + 1;
            while(minSum[index] <= 0){
                sum += minSum[index];
                index = minIndex[index];
                if(index == arr.length)
                    break;
            }
            minSum[i] = sum + arr[i];
            minIndex[i] = index;
        }


        //需要注意当左右指针相遇时要右移右指针

        int right = 0; //表示右边界的下一个位置，指针不回退
        int left = 0;//左边界
        int result = 0;
        int sum = 0;
        while(left < arr.length){//右指针到达了最右边时，左指针还需要继续判断
            if(right == arr.length){
                if(sum <= K){
                    result = Math.max(result, right - left);
                    break;
                }
            }
            if(left == right) {
                sum = minSum[left];
                right = minIndex[left];
            }else if(sum <= K){
                result = Math.max(result, right - left);
                sum += minSum[right];
                right = minIndex[right];
            }else {
                sum -= arr[left];
                left++;
            }
        }
        return result;
    }

    public static int maxLengthAwesome(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] minSums = new int[arr.length];
        int[] minSumEnds = new int[arr.length];
        minSums[arr.length - 1] = arr[arr.length - 1];
        minSumEnds[arr.length - 1] = arr.length - 1;
        for (int i = arr.length - 2; i >= 0; i--) {
            if (minSums[i + 1] < 0) {
                minSums[i] = arr[i] + minSums[i + 1];
                minSumEnds[i] = minSumEnds[i + 1];
            } else {
                minSums[i] = arr[i];
                minSumEnds[i] = i;
            }
        }
        // 迟迟扩不进来那一块儿的开头位置
        int end = 0;
        int sum = 0;
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            // while循环结束之后：
            // 1) 如果以i开头的情况下，累加和<=k的最长子数组是arr[i..end-1]，看看这个子数组长度能不能更新res；
            // 2) 如果以i开头的情况下，累加和<=k的最长子数组比arr[i..end-1]短，更新还是不更新res都不会影响最终结果；
            while (end < arr.length && sum + minSums[end] <= k) {
                sum += minSums[end];
                end = minSumEnds[end] + 1;
            }
            ans = Math.max(ans, end - i);
            if (end > i) { // 还有窗口，哪怕窗口没有数字 [i~end) [4,4)
                sum -= arr[i];
            } else { // i == end,  即将 i++, i > end, 此时窗口概念维持不住了，所以end跟着i一起走
                end = i + 1;
            }
        }
        return ans;
    }

    // for test
    public static int[] generateRandomArray(int len, int maxValue) {
        int[] res = new int[len];
        for (int i = 0; i != res.length; i++) {
            res[i] = (int) (Math.random() * maxValue) - (maxValue / 3);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println("test begin");
        for (int i = 0; i < 10000000; i++) {
            int[] arr = generateRandomArray(10, 20);
            int k = (int) (Math.random() * 20) - 5;
            if (maxLengthAwesome(arr, k) != getMaxLength(arr, k)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }

//    public static void main(String[] args) {
//        int[] arr = {1, 2, -5, 0, -1, -9, 6, 7, 8};
//        int maxLength = getMaxLength(arr, 1);
//        System.out.println(maxLength);
//
//    }
}
